package com.formula.datastructure.exercise.tree;

import com.formula.datastructure.util.DataUtil;

/**
 * Huffman
 */
public class Huffman {


    public Huffman() {
    }

    /**
     * 有几个问题
     * 一是每次都要排序
     * 二是不用数组会简单很多
     *
     * @param array
     * @return
     */
    public HuffmanNode[] buildTree(Integer[] array) {
        int N = array.length;
        HuffmanNode[] nodes = new HuffmanNode[2 * N - 1];
        for (int i = 0; i < N; i++) {
            nodes[i] = new HuffmanNode(array[i]);
        }

        // 要加N-1个节点
        for (int i = 0; i < N - 1; i++) {

            // 找出无parent的最小两个点下标
            int a = -1;
            int b = -1;
            int min1 = 999999;
            int min2 = 999999;
            // 这里很重要, 千万不要忘了N+i, 这个方法就是每次找出最小的两个没有被visited的结点
            for (int j = 0; j < N + i; j++) {
                if (nodes[j].parentIdx == -1 && nodes[j].data < min1) {
                    min2 = min1;
                    // 这一步也很重要, 因为会出现新的值正好比min1和2都小, 必须把min1的值放到min2里面
                    b = a;
                    a = j;
                    min1 = nodes[j].data;
                } else if (nodes[j].parentIdx == -1 && nodes[j].data < min2) {
                    min2 = nodes[j].data;
                    b = j;
                }
            }

            HuffmanNode added = new HuffmanNode(nodes[a].data + nodes[b].data);

            added.leftIdx = a;
            added.rightIdx = b;
            nodes[N + i] = added;

            nodes[a].parentIdx = N + i;
            nodes[b].parentIdx = N + i;
        }

        return nodes;
    }


    public HuffmanLinkNode buildLinkNode(Integer[] array) {
        HuffmanLinkNode node = null;
        int size = array.length;
        HuffmanLinkNode[] list = new HuffmanLinkNode[2 * size - 1];

        for (int i = 0; i < size; i++) {
            list[i] = new HuffmanLinkNode(array[i]);
        }

        int count = 0;
        for (int i = size - 1; i < 2 * size - 2; i++) {
            sortLinkNode(list, count, i);
            HuffmanLinkNode a = list[count];
            HuffmanLinkNode b = list[count + 1];

            HuffmanLinkNode newNode = new HuffmanLinkNode(a.data + b.data);
            list[i + 1] = newNode;
            newNode.left = a;
            newNode.right = b;

            a.parent = newNode;
            b.parent = newNode;
            count = count + 2;
            node = newNode;
        }

        return node;
    }


    private void sortLinkNode(HuffmanLinkNode[] array, int origLow, int origHigh) {
        if (origLow < origHigh) {
            int low = origLow;
            int high = origHigh;
            //low这个位置空出来
            HuffmanLinkNode pivot = array[low];


            while (low < high) {
                while (low < high && pivot.data < array[high].data) {
                    high--;
                }
                // 第一个小的数
                array[low] = array[high];

                while (low < high && pivot.data > array[low].data) {
                    low++;
                }
                array[high] = array[low];
            }
            array[low] = pivot;

            // 中间的这个不用排序
            sortLinkNode(array, origLow, low - 1);
            sortLinkNode(array, low + 1, origHigh);
        }
    }

    // 这种有起始的排序, 适合所有排序法
    private void mergeSort(HuffmanNode[] array, int low, int high) {
    }

    private void quickSort(HuffmanNode[] array, int origLow, int origHigh) {
        if (origLow < origHigh) {
            int low = origLow;
            int high = origHigh;
            HuffmanNode pivot = array[low];

            while (low < high) {
                while (low < high && array[high].data > pivot.data) {
                    high--;
                }
                array[low] = array[high];
                // #1 每次都是和pivot比较
                while (low < high && array[low].data < pivot.data) {
                    low++;
                }
                array[high] = array[low];
            }
            array[low] = pivot;

            quickSort(array, origLow, low - 1);
            quickSort(array, low + 1, origHigh);
        }
    }


    public static void main(String[] args) {
        testHuffmanCode();
    }

    private static void testLinkNode() {
        Integer[] array = DataUtil.genUniqueArray(6, 50);
        DataUtil.printArray(array);
        Huffman tree = new Huffman();
        HuffmanLinkNode root = tree.buildLinkNode(array);
        System.out.println();
    }

    private static void testNode() {
        Integer[] array = DataUtil.genUniqueArray(8, 50);
        DataUtil.printArray(array);
        Huffman tree = new Huffman();
        HuffmanNode[] nodes = tree.buildTree(array);
        System.out.println();
    }

    private static void testHuffmanCode() {
        Integer[] array = DataUtil.genUniqueArray(8, 50);
        DataUtil.printArray(array);
        HuffmanCode code = new HuffmanCode();
        HuffmanLinkNode root = code.genCode(array);
        System.out.println();
    }

}
